//
// Created by 紫霄 on 2020/5/1.
//

#ifndef LEETCODE_67_H
#define LEETCODE_67_H
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (root) {
      vector<TreeNode *> pAns;
      vector<TreeNode *> qAns;
      auto noteP = root;
      auto noteQ = root;
      while (noteP != p) {
        pAns.push_back(noteP);
        if (p->val > noteP->val) {
          noteP = noteP->right;
        } else {
          noteP = noteP->left;
        }
      }
      while (noteQ != q) {
        qAns.push_back(noteQ);
        if (q->val > noteQ->val) {
          noteQ = noteQ->right;
        } else {
          noteQ = noteQ->left;
        }
      }
      int i = 0;
      int sz = pAns.size() > qAns.size() ? qAns.size() : pAns.size();
      while (i < sz) {
        if (pAns[i] == qAns[i]) {
          ++i;
        } else {
          break;
        }
      }
      return pAns[i - 1];
    }
    return root;
  }
};
#endif // LEETCODE_67_H
